#include<iostream>
#include<vector>
using namespace std;
int criterion(vector<int>& arr, int left, int right)
    {
        //该函数返回的是基准的下标
        int x = left;
        int val = arr[x];
        while (left < right)
        {
            while (left < right && arr[right] >= val)
            {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= val)
            {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = val;
        return left;
    }
    void quicksort(vector<int>& arr, int left, int right)
    {
        if (right <= left)
            return;
        int x = criterion(arr, left, right);
        quicksort(arr, left, x - 1);
        quicksort(arr, x + 1, right);
    }
    vector<int> MySort(vector<int>& arr)
    {
        int len = arr.size();
        if (len == 1)
            return arr;
        quicksort(arr, 0, len - 1);
        return arr;
    }
    int main()
    {
        // 测试示例
        vector<int> arr = { 5, 2, 8, 1, 9, 3, 7, 4, 6 };
        cout << "排序前: ";
        for (int num : arr) {
            cout << num << " ";
        }
        cout << endl;
        // 调用排序函数
        MySort(arr);
        cout << "排序后: ";
        for (int num : arr) {
            cout << num << " ";
        }
        cout << endl;
        return 0;
    }